#include <algorithm>
using namespace std;

struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right)
      : val(x), left(left), right(right) {}
};

int getHeight(TreeNode *root) {
  if (root == nullptr)
    return 0;
  int l = getHeight(root->left);
  if (l == -1)
    return -1;
  int r = getHeight(root->right);
  if (r == -1) {
    return -1;
  }
  if (abs(l - r) <= 1) {
    return max(l, r) + 1;
  } else {
    return -1;
  }
}

bool isBalanced(TreeNode *root) {
  if (!root)
    return true;
  int l = getHeight(root->left);
  int r = getHeight(root->right);
  if (l == -1 || r == -1)
    return false;
  return abs(l - r) <= 1;
}